The invention relates to a real time analysis of a computer system.
The analysis of the time-based behavior of embedded real-time systems is needed in order to automate the development of such systems. Not only the correct but also the timely determination of the computation results is necessary for the correct function of real-time systems. Examples of such systems are airbag control or motor control.
A model of tasks communicating with each other as per FIG. 1 will be considered. In this connection, a “task” is a series of processing steps which processes a set of input values and, in doing so, generates computation results or changes to the system. A task can be represented by an algorithmic description or a description of one piece of hardware executing the functionality. In this connection, tasks can activate other tasks which, for example, further process the computation results of the activating task. Tasks can also access resources. The activations or resource accesses can take place at any point during the execution of the task. The activations of a task or the resource access will now be referred to as “event”.
To be able to perform quick analyses for such a model, a description of the “occurrence behavior of events” is needed. “Occurrence behavior of events” is understood to mean the time-based occurrence behavior, in other words, the time intervals between a plurality of events. “Occurrence pattern” is understood to mean a description of the occurrence behavior. The “occurrence pattern” comprises a plurality of description elements. The description elements can be the same or different; they each represent a portion of the “occurrence behavior of the events.” A possible description of an “occurrence pattern” is the so-called “event density.” Aside from this, it is also possible to describe an “occurrence pattern”, for example, as a period or a jitter.
With the description form of the “event density,” the maximum/minimum number of events is specified in time intervals of a specified length. In this connection, the event density can be subject to fluctuations.
Moreover, the description should also support a quick analysis of the time-based behavior, in particular the guaranteed adherence to specified time limits. It is particularly important to quickly determine from a description of the “occurrence behavior of events” for specified intervals the number of events occurring in this and for specified numbers of events an interval in which this number can occur. In this connection, usually only the lengths of the intervals are significant and maximum or minimum interval lengths are needed for certain numbers of events, or maximum or minimum numbers of events are needed for certain interval lengths. In this connection, descriptions that permit this determination with a linear complexity regarding the number of elements of the description are particularly advantageous.
Many papers in this area use a purely periodic occurrence pattern.
From K. Gresser. Echtzeitnachweis Ereignisgesteuerter Real-zeitsysteme. Dissertation, VDI Verlag, Dusseldorf, 10 (286), 1993, a description for occurrence patterns of events is known which is designated as an event stream model. In this connection, an “event stream” is described by a set of tuples, each consisting of a cycle z and a distance a. The tuples can be designated as “event stream elements”. The distance to an origin specified the same for event stream elements is assumed. Each event stream element generates its own occurrence pattern, wherein the first event of the event stream element can occur at a distance a from the common origin and each of the subsequent events then follow displaced by the cycle z. Thus the second event can follow at the distance of a+z from the origin, the third event at a+2z and so forth. The total event stream results from a superposition of the occurrence patterns of all event stream elements. Furthermore, only those event streams are considered valid in the task that generate an occurrence pattern for which the greatest densities of events each begin at the origin. Hence, the initial distance zero must be assigned to at least one event stream element. In this connection, it is assumed that the event stream describes an upper limit for a “maximum occurrence pattern” of events. A “maximum occurrence pattern” is understood to mean an occurrence pattern which has a maximum possible event density. During the real sequence, a less dense occurrence of the events in a system than that described by the event stream is considered permissible. In this connection, permissible means that time limits whose adherence to can be guaranteed for the event stream, and can also be adhered to for the decreased event density. A real-time analysis method will be described for this model.
In later works (K. Albers, F. Slomka. An Event Stream Driven Approximation for the Analysis of Real-Time Systems. IEEE Proceedings of the 16th Euromicro Conference on Real-Time Systems, 2004, p, 187-195; K. Albers, F. Slomka. Efficient Feasibility Analysis for Real-Time Systems with EDF-Scheduling. Proceedings of the Design Automation and Test Conference in Europa (DATE'05) p. 492-497), a very efficient real-time analysis is described for this. The problem of this description is that event bursts cannot be efficiently represented and thus also not efficiently analyzed. An “event burst” is understood to mean a limited time increase in density of events within one “occurrence pattern.” The event stream model requires that each event within an event burst must be represented by its own event stream element. Only when event bursts repeatedly occur periodically within an occurrence pattern is it sufficient to assign to the events of the first event burst an event stream element, respectively. Since event bursts can comprise thousands of elements, the event stream model is not suitable as a description form for such systems.
In S. Chakraborty, L. Thiele, A New Task Model for Streaming Applications and its Schedulability Analysis, IEEE Proceedings of the Design Automation and Test in Europe Conference (DATE'05), pp. 486-491, 2005, a possible description for occurrence patterns is presented which is specialized for an efficient representation of event bursts. The occurrence patterns are again described by a set of tuples. In this model, these consist of a number of events and an interval, and specify the maximum number of events which can occur in an interval of this length. In this connection, the individual tuples mutually restrict each other so that only occurrence patterns are permitted that satisfy all tuples. Certain event bursts can be described efficiently with this model. However, the problem with the description is that the suggested analysis requires a stipulation of many linear combinations of all tuples and thus cannot be performed efficiently. Furthermore, many kinds of event bursts cannot be efficiently represented by the model. An occurrence pattern for which, for example, the first two events occur at a distance t from each other and all other events occur at a distance 1>t from their respective previous event, cannot be represented efficiently by this model. Each event except the first would have to be described by its own tuple. Furthermore, such occurrence patterns in which event bursts with different internal occurrence patterns occur cannot be described.
In K. Richter, Compositional Scheduling Analysis Using Standars Event Models, dissertation, TU Braunschweig, 2005, a description is presented in which the events are described by a period, an event jitter and a minimum distance between events. In this connection, the “event jitter” describes a time interval in which the principal periodic occurrences can fluctuate. When the event jitter comprises a plurality of periods, all those events which occur within the time interval can occur almost simultaneously. They are only separated by the minimum distance.
This model can be used to describe a simple, initially occurring event burst with a simple minimum distance between the events within the event burst. More complex event bursts which, for example, can occur repeatedly, or event bursts with a more complex occurrence pattern of the events within the event burst cannot be represented with this description.